package leetcode.code1475;

import java.util.Stack;

public class Solution {
	public int[] finalPrices(int[] prices) {
		Stack<Integer> s = new Stack<>();
		int len = prices.length;
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			int cur = prices[i];
			while (!s.isEmpty() && cur <= prices[s.peek()]) {
				int index = s.pop();
				ans[index] = prices[index] - cur;
			}
			s.add(i);
		}
		while (!s.isEmpty()) {
			int index = s.pop();
			ans[index] = prices[index];
		}
		return ans;
	}
}
